/*
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Anser:748317
Time:27.123335ms
*/

package main

import (
	"fmt"
	"time"
)

const bound = 1e6

var s = [bound]bool{}

func main() {
	tstart := time.Now()
	prime()
	sum := 0
	for i := 10; i < bound; i++ {
		if leftPrime(i) && rightPrime(i) {
			//fmt.Println(i)
			sum += i
		}
	}
	fmt.Println(sum)
	tend := time.Now()
	fmt.Println(tend.Sub(tstart))
}

//prime 将切片s下标设置成是否不为质数
func prime() {
	s[0] = true
	s[1] = true
	for i := 2; i < bound; i++ {
		if !s[i] {
			for j := 2; i*j < bound; j++ {
				s[i*j] = true
			}
		}
	}
}

// rightPrime 判断abcd，abc，ab，a是否都是质数
func rightPrime(n int) bool {
	for i := 1; i < n; i *= 10 {
		if s[n/i] {
			return false
		}
	}
	return true
}

// leftPrime 判断abcd，bcd，cd，d是否都是质数
func leftPrime(n int) bool {
	for i := 10; i < n; i *= 10 {
		if s[n%i] {
			return false
		}
	}
	return true
}
